class Solution26 {
    public static boolean check[][];
    public static boolean exist(char[][] board, String word) {
        check = new boolean[board.length][board[0].length];
        return dfs(board,0,0,word,0);
    }
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};

    public static boolean dfs(char[][] board, int x, int y, String word, int pos) {
        if(pos == word.length()) {
            return true;
        }
        if(pos == 0) {
            for(int i = x; i < board.length; i++) {
                for(int j = y; j < board[0].length; j++) {
                    if(check[i][j] == false && word.charAt(pos) == board[i][j]) {
                        check[i][j] = true;
                        if(dfs(board,i,j,word,pos+1) == true) return true;
                        check[i][j] = false;
                    }
                }
            }
        }

        //写法一
        for(int k = 0; k < 4; k++) {
            int x1 = dx[k] + x;
            int y1= dy[k] + y;
            if(x1 >= 0 && x1 < board.length && y1 >= 0 && y1 < board[0].length && check[x1][y1] == false && word.charAt(pos) == board[x1][y1]) {
                check[x1][y1] = true;
                if(dfs(board,x1,y1,word,pos+1) == true) return true;
                check[x1][y1] = false;
            }
        }
        
        /*//向上  向下  向左   向右   写法二
        if(x-1 >= 0 && y >= 0 && x-1 < board.length && y < board[0].length && check[x-1][y] == false && word.charAt(pos) == board[x-1][y]) {
            check[x-1][y] = true;
            if(dfs(board,x-1,y,word,pos+1) == true) return true;
            check[x-1][y] = false;
        }

        if(x+1 < board.length && x+1 >= 0 && y < board[0].length && y >= 0 &&check[x+1][y] == false && word.charAt(pos) == board[x+1][y]) {
            check[x+1][y] = true;
            if(dfs(board,x+1,y,word,pos+1) == true) return true;
            check[x+1][y] = false;
        }

        if(y-1 >= 0 && y-1 < board[0].length && x >= 0 && x < board.length && check[x][y-1] == false && word.charAt(pos) == board[x][y-1]) {
            check[x][y-1] = true;
            if(dfs(board,x,y-1,word,pos+1) == true) return true;
            check[x][y-1] = false;
        }

        if(y+1 < board[0].length && y+1 >= 0 && x <board.length && x >= 0 && check[x][y+1] == false && word.charAt(pos) == board[x][y+1]) {
            check[x][y+1] = true;
            if(dfs(board,x,y+1,word,pos+1) == true) return true;
            check[x][y+1] = false;
        }*/
        return false;
    }

    public static void main(String[] args) {
        char[][] word = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        boolean tf = exist(word,"ABCCED");
        System.out.println(tf);
    }
}